package random_test;

import java.util.*;

class ListNode {
    int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Test_9_4 {


    //2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode lastNode  = head;
        int carry = 0;
        while(l1 != null || l2 != null) {
            int num1 = (l1 != null)?l1.val:0;
            int num2 = (l2 != null)?l2.val:0;
            int sum = num1 + num2 + carry;
            lastNode.next = new ListNode(sum % 10);
            lastNode = lastNode.next;
            carry = sum / 10;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        if(carry != 0) {
            lastNode.next = new ListNode(carry);
        }
        return head.next;
    }


    //3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;

        Set<Character> set = new HashSet<>();
        int left = 0;
        int right = -1;
        int max = 0;
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(!set.contains(ch)) {
                set.add(ch);
                right++;
            }else {
                if(max < right-left+1) {
                    max = right-left+1;
                }
                while(set.contains(ch)) {
                    set.remove(s.charAt(left));
                    left++;
                }
                set.add(ch);
                right++;
            }
        }
        if(max < right - left + 1) max = right - left + 1;
        return max;
    }
}
